We show that for every positive $\epsilon > 0$, unless NP $\subset$ BPQP, itis impossible to approximate the maximum quadratic assignment problem within afactor better than $2^{\log^{1-\epsilon} n}$ by a reduction from the maximumlabel cover problem. Our result also implies that Approximate Graph Isomorphismis not robust and is in fact, $1 - \epsilon$ vs $\epsilon$ hard assuming theUnique Games Conjecture. Then, we present an $O(\sqrt{n})$-approximation algorithm for the problembased on rounding of the linear programming relaxation often used in the stateof the art exact algorithms.
展开▼
